<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>整数, 有理数, 代数数, 连分数</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>整数</h2>

<p class="definition">
	<b>自然数</b>又叫<b>正整数</b>, 即熟知的
	<span class="formula">
		`1, 2, 3, cdots, n, cdots`.
	</span>
	用 `NN` 表示全体自然数的集合.
	<br/>
	<b>整数</b>是指正整数, 负整数及零, 即
	<span class="formula">
		`0, +-1, +-2, +-3, cdots, +-n, cdots`.
	</span>
	用 `ZZ` 表示全体整数的集合.
</p>

<h3>整数的运算</h3>

<ol class="enum">
	整数集合 `ZZ` 关于其上的加法 "`+`" 与乘法 "`*`" 成一<b>整环</b>, 即
	<li>
	关于加法与乘法成一环.
	<ol>
		关于加法成一 Abel 群.
		<li>封闭性. `(AA a, b in ZZ)` `a + b in ZZ`;</li>
		<li>结合律. `(AA a, b, c in ZZ)` `(a+b)+c = a+(b+c)`;</li>
		<li>存在零元. `(EE 0 in ZZ)`, `(AA a in ZZ)` `a + 0 = a`;</li>
		<li>存在负元. `(AA a in ZZ)`, `(EE -a in ZZ)` `a + (-a) = 0`;</li>
		<li>交换律. `(AA a, b in ZZ)`, `a+b = b+a`;</li>
		关于乘法成一半群.
		<li>封闭性. `(AA a, b in ZZ)` `a * b in ZZ`;</li>
		<li>结合律. `(AA a, b, c in ZZ)` `(a*b)*c = a*(b*c)`;</li>
		满足乘法对加法的分配律:
		<li>`(AA a, b, c in ZZ)` `a * (b + c) = a*b + a*c`.</li>
	</ol>
	</li>
	<li>无零因子. `(AA a, b in ZZ)` `a * b = 0 rArr a = 0 or b = 0`;</li>
	<li>乘法交换律. `(AA a, b in ZZ)` `a*b = b*a`;</li>
	<li>有乘法幺元. `(EE 1 in ZZ)` `(AA a in ZZ)` `a * 1 = a`;
		但是, 不一定有乘法逆元.
	</li>
	因此, 也称 `ZZ` 为<b>整数环</b>.
	简单起见, 字母间的乘法 `a*b` 简记为 `ab`,
	减法 `a + (-b)` 简记为 `a-b`.
</ol>

<p>从整数乘法的无零因子可以推出它满足的消去律:
	<span class="formula">
		`(AA a in ZZ\\{0}, b, c in ZZ)` `a*b = a*c rArr b = c`.
	</span>
</p>

<h3>整数的序</h3>

<ol class="enum">整数环 `ZZ` 上有一<b>全序</b> `le`, 即满足
	<br/>
	<li>`le` 为一偏序.
	<ol>
		<li>自反性. `(AA a in ZZ)` `a le a`;</li>
		<li>反对称性. `(AA a, b in ZZ)` `a le b and b le a rArr a =
			b`;
		</li>
		<li>传递性. `(AA a, b, c in ZZ)` `a le b and b le c rArr a le
			c`.
		</li>
	</ol>
	据此可以定义 `ge, lt, gt` 如下: 对 `a, b in ZZ`,
	<span class="formula">
		`a ge b iff b le a`;<br/>
		`a lt b iff a le b and a != b`;<br/>
		`a gt b iff a ge b and a != b`.
	</span>
	</li>

	<li>任意两个整数之间可以比较大小.
		`AA a, b in ZZ`, `a=b, a lt b, a gt b` 有且仅有一个成立.
	</li>
</ol>

<ol>全序 `le` 与 `ZZ` 上的运算<b>相容</b>, 即
	<li>`(AA a, b, c in ZZ)` `a + c le b + c iff a le b`;</li>
	<li>`(AA a, b in ZZ, c in NN)` `a c le b c iff a le b`;</li>
	<li>`(AA a, b in ZZ)` `a le b iff -a ge -b`;</li>
</ol>

<ol>一些额外的性质
	<li>`(AA a, b, c in NN)` `c = ab rArr a le c`, 等号成立当且仅当 `b =
		1`.
	</li>
	<li>`(AA a, b in NN)` `a lt b iff a + 1 le b iff a le b-1`.</li>
</ol>

<h3>整数的绝对值</h3>

<p class="definition">
	对任意 `a in ZZ`, 定义它的<b>绝对值</b>为
	<span class="formula">
		`|a| = {
			a, if a in NN;
			0, if a = 0;
			-a, if -a in NN;
		:}`
	</span>
</p>

<ol>借助绝对值容易建立等价关系 `~: a ~ b iff |a| = |b|`, 满足
	<li>自反性. `(AA a in ZZ)` `a ~ a`;</li>
	<li>对称性. `a ~ b rArr b ~ a`;</li>
	<li>传递性. `a ~ b and b ~ c rArr a ~ c`.</li>
</ol>

<p>	绝对值具有性质
	<span class="formula">
		`|ab| = |a| * |b|`, `AA a, b in ZZ`;<br/>
		`|a + b| le |a| + |b|`. `AA a, b in ZZ`.
	</span>
</p>

<h3>归纳原理与数学归纳法</h3>

<ol><b>归纳原理</b>
	设 `S sube NN` 满足条件
	<li>`1 in S`;</li>
	<li>`n in S rArr n+1 in S`, `AA n ge 1`,</li>
	则 `S = NN`.
</ol>

<p>	归纳原理是自然数最重要, 最本质的性质.
</p>

<ol class="theorem">
	<b>(第一) 数学归纳法</b>
	设 `P(n)` 是关于自然数 `n` 的一种性质或命题. 如果
	<li>`P(1)` 成立;</li>
	<li>由 `P(n)` 成立可以推出 `P(n+1)` 成立, `AA n ge 1`,</li>
	那么 `P(n)` 对任意的自然数 `n` 成立.
</ol>

<p class="proof">
	对集合 `S = {n in NN: P(n)}` 应用归纳原理即得.
</p>

<ol class="theorem">
    <li><b>最小自然数原理</b> `NN` 的任意非空子集中存在最小元;</li>
    <li><b>最大自然数原理</b> `NN` 的任意非空且在 `NN` 中有上界的子集中存在最大元.</li>
</ol>

<ol class="proof">
    <li>设 `O/ != S sube NN`, 要证
        <span class="formula">
            `(EE m in S)` `(AA s in S)` `m le s`.
        </span>
        令 `L` 是 `S` 的全体<b>下界</b>, 即
        <span class="formula">
            `L = {l in NN: (AA s in S) l le s}`.
        </span>
        易知 `1 in L`, 故 `L` 非空.<br/>
        由于 `S` 非空, 取 `s in S`, 有 `s+1 gt s`.
        所以 `s+1 !in L`, 这说明 `L != NN`.
        由归纳原理, 存在 `m in L`, `m+1 !in L`.<br/>
        下证 `m in S`.  若不然, 则对任意 `s in S`, `m lt s`,
        即 `m+1 le s`, 故 `m+1 in L`, 矛盾.
        `m` 即为 `S` 中的最小自然数.
    </li>
    <li>设 `O/ != S sube NN` 且在 `NN` 中有上界, 要证
        <span class="formula">
            `(EE M in S)` `(AA s in S)` `s le M`.
        </span>
        令
        <span class="formula">
            `U = {u in NN: (AA s in S) s le u}`
        </span>
        是 `S` 的全体上界, 则 `U` 非空.
        由最小自然数原理知, `U` 中有最小自然数 `M`.
        下证 `M in S`, 若不然, 则对任意 `s in S`, `s lt M`, 即 `s le M-1`.
        从而 `M-1 in U`, 与 `M` 是 `S` 的最小上界矛盾.
        `M` 即为 `S` 中的最大自然数.
    </li>
</ol>

<p class="remark">
	从证明过程可以看出,
	整数集合中的最小自然数与最大自然数分别等于其下确界与上确界.
</p>

<ol class="theorem">
	<b>第二数学归纳法</b>
	设 `P(n)` 是关于自然数 `n` 的一种性质或命题. 如果
	<li>`P(1)` 成立;</li>
	<li>由 `P(m)` 对任意自然数 `m lt n` 成立可以推出 `P(n)` 成立, `n gt 1`,</li>
	那么 `P(n)` 对任意的自然数 `n` 成立.
</ol>

<p class="proof">
	反设集合 `T = {t in NN: not P(t)}` 非空, 则它有最小元 `t_0`,
	由 `P(1)` 成立知 `t_0 gt 1`,
	于是对任意自然数 `m lt t_0`, `P(m)` 成立,
	由2, 这蕴含 `P(t_0)` 成立, 矛盾.
</p>

<p>	本节的最后介绍初等数论中另一个常用的工具. 这可以由反证法得到.</p>

<p class="theorem">
    <b>抽屉原理 (鸽巢原理)</b>
	设 `n in NN`. 集合 `X` 有 `n+1` 个元素, 集合 `Y` 有 `n` 个元素,
	则 `X` 到 `Y` 的映射一定不是单射. 换言之, 将 `n+1` 个物体放入 `n`
	个盒子, 一定有一个盒子放入了两个或两个以上的物体.
</p>

<p class="theorem">
    <b>Dirichlet 逼近定理</b>
    设 `x in RR`, `n in ZZ^+`, 则在 `x, 2x, cdots, n x` 这 `n` 个数中,
    存在一个数, 到最近整数的距离小于 `1//n`.
</p>

<p class="proof">
    记 `{x} = x - [x]` 为实数 `x` 的小数部分.
    考虑 `n+1` 个数
    <span class="formula">
        `0, {x}, {2x}, cdots, {n x}`,
    </span>
    它们落在区间 `[0, 1)` 中. 若将区间平均分为 `n` 份
    <span class="formula">
        `[0, 1//n)`, `cdots`, `[(n-1)//n, 1)`,
    </span>
    则必有两个数落在同一区间. 设它们是 `{i x}`, `{j x}`, 其中
    `0 le j lt i le n`, 则
    <span class="formula">
        `1//n gt |{i x} - {j x}|`
        `= |i x - [i x] - j x + [j x]|`
        `= |(i-j) x - ([i x] - [j x])|`.
    </span>
    令 `k = i-j`, `m = [i x] - [j x]`, 则 `1 le k le n`, 且
    `k x` 到 `m` 的距离小于 `1//n`.
</p>

<p class="example">
    设整数 `n gt 1`. 证明: `H_n = sum_(j=1)^n 1/j` 不是整数.
</p>

<ol class="proof">
    利用如下事实:
    每个正整数 `j` 都可以唯一地写为 `j = 2^(m_j) a_j`,
    其中 `m_j ge 0`, `a_j` 为奇数.
    <li>下证 `m_j` 在 `1 le j le n` 中有唯一的最大值 `m`.
        设 `m_j = m_k = m`, `j le k`, 则
        <span class="formula">
            `k - j = 2^(m_k) a_k - 2^(m_j) a_j`
            `= 2^m (a_k - a_j)`,
        </span>
        其中 `a_k, a_j` 为奇数, 因此 `k - j` 为偶数. 若 `k - j gt 0`,
        则它所含的 2 的次数大于 `m`, 矛盾; 因此 `k = j`.
    </li>
    <li>设 `m = m_k = max_(1 le j le n) m_j`,
        `M = 2^(m-1) prod a_j`. 由 1. 知,
        `j = 2^(m_j) a_j | M` 当且仅当 `j != k`. 于是
        <span class="formula">
            `M H_n = sum M/j -= M/k (mod 1)`
        </span>
        上式右边不是整数, 因此左边也不能是整数, 证毕.
    </li>
</ol>

<h3>取整函数</h3>

<p class="lemma">
  <b>阿基米德 (Archimedes) 原理</b>
  对任意实数 `a` 和 `epsi gt 0`, 存在正整数 `n` 使得 `n epsi gt a`.
</p>

<p class="proof">
  考虑集合 `S = { n epsi | n in ZZ^+ }`.
  若不存在正整数 `n` 使得 `n epsi gt a`, 那么 `a` 是 `S` 的上界;
  由确界原理, 可设 `S` 的上确界为 `A`. 则存在 `n_0 epsi in S` 使得
  <span class="formula">
    `n_0 epsi gt A - epsi`,
  </span>
  即 `(n_0+1) epsi gt A`. 但 `(n_0+1) epsi in S`, 这与 `A` 是 `S`
  的上确界矛盾.
</p>

<p class="corollary">
  任意给定实数 `x`, 都存在整数 `m, n` 满足 `m lt x lt n`.
</p>

<p class="proof">
  在 Archimedes 原理中特别取 `epsi = 1` 知, 任意给定一个实数 `x`,
  总能找到一个正整数 `n` 大于它. 另一方面, 对于实数 `-x`, 存在正整数 `-m`
  使得 `-m gt -x`. 综上 `m lt x lt n`.
</p>

<p class="definition">
  对任意实数 `x`, 集合 `{n in ZZ| n ge x}` 和 `{m in ZZ| m le x}` 都非空,
  且前者在 `ZZ` 中有下界, 后者在 `ZZ` 中有上界.
  故定义 `x` 的<b>向上取整</b> `|~ x ~|` 为不小于 `x`
  的最小正整数, <b>向下取整</b> `|__x__|` 为不大于 `x` 的最大正整数.
</p>

<p class="example">
    已知正整数 `c`, 求正整数 `n` 满足
    <span class="formula">
        `(n(n-1))/2 le c lt (n(n+1))/2`.
    </span>
</p>

<p class="solution">
    解二次不等式得
    <span class="formula">
        `(-1+sqrt(1+8c))/2 lt n le (1+sqrt(1+8c))/2`,
    </span>
    即 `n = |__(1+sqrt(1+8c))/2__|`.
    注意分母为 2, 因此分子每变化 2,
    才引起 `n` 的一次跳跃, 我们可以用取整平方根代替平方根,
    即 `n = |__(1+|__sqrt(1+8c)__|)/2__|`.
</p>

<h2>有理数与无理数</h2>

<p class="theorem">
	无限循环小数是有理数; 反之, 有理数 `m//n` 可以写成无限循环小数,
	且循环节的长度小于分母 `n`. 因此,
	一个数是无理数当且仅当它是无限不循环小数.
</p>

<ol class="proof">
	<li>不妨设这个 `B` 进制小数 (`B gt 1`) 在区间 `[0, 1]` 中.
		则它可以写成 `0.a_1 a_2 cdots a_k {:dot a:}_(k+1) cdots
		{:dot a:}_(k+p)`. 记
		<span class="formula">
			`m_1 = a_(k+1) cdots a_(k+p)`
			`= sum_(i=1)^p a_(k+i) B^(p-i)`.
		</span>
		原来的小数等于
		<span class="formula">
			`sum_(i=1)^k a_i B^-i + B^-k sum_(j=1)^oo B^(-p j) m_1`
			`= sum_(i=1)^k a_i B^-i + B^-k/(B^p-1) m_1`,
		</span>
		故是一个有理数.
	</li>
	<li>(证明参考初等数论的例题)
		不妨设 `n gt 1`.
		如果存在正整数 `k` 使得 `n | B^k`, 设 `B^k = n_1 n`, 则
		`m//n = m n_1 // B^k` 是一个有限小数. 否则有
		`n !| B^k`, `k = 0, 1, cdots, n-1`. 设 `B^k` 除以 `n` 的余数是
		`r_k`, 则 `n` 个数
		<span class="formula">
			`r_0, r_1, cdots, r_(n-1)`
		</span>
		只能取 `1, 2, cdots, n-1` 这 `n-1` 个值. 由鸽巢原理,
		必有两个余数相等, 设为 `r_i = r_j`, `0 le j lt i lt n`. 则
		<span class="formula">
			`n | B^i - B^j = B^j(B^(i-j)-1)`.
		</span>
		设 `d = i-j`, `B^j(B^d-1) = n n_2`, 则
		<span class="formula">
			`m/n = (m n_2)/(B^j(B^d-1))`.
		</span>
		记 `m_2 = m n_2`. 下面只需证 `m_2/(B^d-1)` 是循环小数.
		我们只看小数部分, 不妨设 `0 le m_2/(B^d-1) le 1`,
		于是 `0 le m_2 le B^d-1`.
		将 `m_2` 表为 `B` 进制数 (在前面添加 0 直到有 `d` 位数)
		<span class="formula">
			`m_2 = sum_(j=1)^d a_j B^(d-j) = a_1 a_2 cdots a_d`,
		</span>
		得到
		<span class="formula">
			`m_2/(B^d-1) = sum_(i=1)^oo B^(-d i) m_2`
			`= 0.a_1 a_2 cdots a_d a_1 a_2 cdots a_d cdots`.
		</span>
		这是循环节长度为 `d` 的循环小数, 其中 `d = i-j lt n`.
	</li>
</ol>

<p class="example">
	`sqrt 2` 是无理数.
</p>

<p class="proof">
	(Euclid 的证明) 反设 `sqrt 2 = a//b`, `a, b` 是互素的整数. 两边平方得
	<span class="formula">
		`2b^2 = a^2`.
	</span>
	`a^2 = 2b^2` 是偶数, 所以 `a` 也是偶数, 设 `a = 2n`, 于是
	<span class="formula">
		`2b^2 = (2n)^2`, `quad b^2 = 2n^2`.
	</span>
	应用同样的推理知 `b` 是偶数, 从而 `a`, `b` 有公因子 `2`. 矛盾.
</p>

<p class="theorem" id="the-rational-root">
    记整系数多项式的有理根 (如果存在) 的最简分数为 `c//d`,
    则 `d` 是首项系数的因子, `c` 是常数项的因子.
    特别首项系数为一的整系数多项式, 其有理根 (如果存在) 必为整数,
    且这个整数是常数项的因子.<br/>
    例如 `d x - c` 的根为 `c//d`, 其中分母是首项的因子,
    分子是常数项的因子.
</p>

<p class="proof">
    设 `f(x) = a_n x^n + cdots + a_1 x_1 + a_0`.
    将 `x = c//d` 代入, 两边同乘 `d^n` 得
    <span class="formula">
        `a_n c^n + cdots + a_1 c d^(n-1) + a_0 d^n = 0`,
    </span>
    从而 `d | a_n c^n`. 但 `(c, d) = 1`, 所以 `d | a_n`. 同理
    `c | a_0 d^n rArr c | a_0`.
</p>

<p class="corollary">
	设 `n, k` 是正整数. 则 `root k n` 是整数或无理数.
    因此, `sqrt 2, sqrt 5, sqrt 12, root 3 2` 都是无理数.
</p>

<p class="proof">
    注意 `root k n` 是多项式 `x^k - n` 的根. 若它为有理数, 则必为整数.
</p>

<p class="proof">
	显然 `n gt 1`, 设 `p` 是 `n` 的一个素因子, 且 `p^k !| n` (如果 `n`
	的所有素因子的次数都至少是 `k`,	我们可以将它们同时从根号下提出, 比如
	`sqrt 72 = 6 sqrt 2`, 这样就转化为证明 `sqrt 2` 是无理数了).
	我们反设 `root k n = a//b`, `a, b` 互素. 下面证明 `a,b` 至少有公因子
	`p`, 从而引出矛盾.<br/>
	两边 `k` 次方得 `n b^k = a^k`, 于是 `p | a^k`, 这推出 `p | a`, 进而
	`p^k | a^k = n b^k`.
	因为 `n` 中含因子 `p` 的次数小于 `k`, 我们推出 `p | b^k`, 于是 `p
	| b`, 即 `p` 是 `a, b` 的公因子.
</p>

<p class="corollary">
    `a^n | b^n rArr a | b`.
</p>

<p class="proof">
    设 `b^n = a^n d`, 则 `b/a = root n d` 是整数.
</p>

<p class="example" id="exp-a^2|kb^2">
  `a, b, k` 为正整数, `k` 无平方因子, 且 `a^2 | k b^2`. 证明: `a | b`.
</p>

<p class="proof">
  因为我们可以从 `a^2 | k b^2` 两边同时约去 `a, b` 的最大公因数,
  所以不妨设 `(a, b) = 1`. 于是 `a^2 | k`, 但 `k` 无平方因子, 得到 `a^2
  = 1`, 从而 `a = 1`, `a | b`.
</p>

<p class="example">
	设 `a, b` 是两个不同的正整数, 若 `sqrt a, sqrt b` 有一个是无理数,
	则 `sqrt a +- sqrt b` 都是无理数. 因此 `sqrt 2 + 1`, `sqrt 2 + sqrt
	3`, `(sqrt 5-1)/2` 都是无理数.
</p>

<p class="proof">
	记 `u, v = sqrt a +- sqrt b`, 则 `u v` 是有理数. 假设 `u, v`
	中有一个有理数, 则 `u, v` 都是有理数, 从而
	<span class="formula">
		`sqrt a, sqrt b = (u+-v)//2`
	</span>
	都是有理数. 矛盾.
</p>

<p class="example">
  若 `a, b` 是大于 1 的正整数, `a, b` 互素, 则 `log_a b` 是无理数.
</p>

<p class="proof">
  反设 `log_a b = m//n`, 则 `a^m = b^n`, 由 `a, b` 互素得 `a = b = 1`, 矛盾.
</p>

<ol class="theorem">
	<li>存在两个无理数 `a, b`, 使得 `a^b` 是有理数;</li>
	<li>存在两个无理数 `a, b`, 使得 `(a b)/a^b` 是有理数.</li>
</ol>

<ol class="proof">
	设 `s = sqrt 2`.
	<li>若 `s^s` 是有理数, 取 `a = b = s` 即得证.
		否则 `s^s` 是无理数, 取 `a = s^s`, `b = s`, 有
		<span class="formula">
			`a^b = (s^s)^s = s^(s^2) = s^2 = 2`.
		</span>
	</li>
	<li>若 `s^(s+1)` 是有理数, 则 `s^s` 是无理数. 取 `a = s^s`, `b = s`
		即得证. 否则 `s^(s+1)` 是无理数, 取 `a = s^(s+1)`, `b = s` 即得证.
	</li>
</ol>

<p class="proof">
  第一小题的更具体的例子: `sqrt 2` 的 `log_2 9` 次方等于 `3`.
</p>

<p class="theorem" id="the-e-irrational">
  [<a href="https://zhuanlan.zhihu.com/p/68095343">来自 知乎</a>]
	`"e"` 是无理数.
</p>

<p class="proof">
	反设 `"e" = a//b`, `a, b` 为正整数. 取正整数 `n gt b`, 则
	<span class="formula">
		`n! b "e" = n! a`.
	</span>
	显然上式右端为整数. 利用级数 `"e" = sum_(k=0)^oo 1/(k!)`, 上式左端等于
	<span class="formula">
		`n! b sum_(k=0)^n 1/(k!) + n! b sum_(k=n+1)^oo 1/(k!)`
		`:= A + B`.
	</span>
	显然第一项 `A` 为整数, 然而
	<span class="formula">
		`0 lt B = b sum_(k=n+1)^oo (n!)/(k!)`
		`lt b sum_(k=1)^oo 1/(n+1)^k`
		`= b/n lt 1`.
	</span>
	因此 `B` 不可能是整数, 矛盾.
</p>

<ol class="lemma">
	设 `n` 为正整数. 函数 `f(x) = (x^n(1-x)^n)/(n!)` 满足:
	<li>`f(x)` 是一个形如 `sum_(i=n)^(2n) c_i/(n!) x^i` 的多项式, 且 `c_i`
		是整数, `i = n, n+1, cdots, 2n`;
	</li>
	<li>`0 lt f(x) lt 1/(n!)`, `AA x in (0, 1)`;</li>
	<li>`f^((m))(0)`, `f^((m))(1)` 都是整数, `m = 0, 1, 2, cdots`.</li>
</ol>

<p class="proof">
	性质 1, 2 显然. 下证性质 3.
	`m lt n` 或 `m gt 2n` 时, 注意 `f(x)` 低于 `n` 次和高于 `2n`
	次的项的系数全为零, 因此 `f^((m))(0) = 0` 是整数.
	`n le m le 2n` 时, 求导得
	<span class="formula">
		`f^((m))(0) = c_m (m!)/(n!)`,
	</span>
	也为一整数. 利用对称性 `f(x) = f(1-x)`,
	<span class="formula">
		`f^((m))(x) = (-1)^m f^((m))(1-x)`
	</span>
	取 `x = 1` 知道, `f^((m))(0)` 是整数时, `f^((m))(1)` 也是整数. 证毕.
</p>

<p class="theorem">
	`AA k in ZZ^+`, `"e"^k` 是无理数.
</p>

<p class="proof">
	假设存在正整数 `k`, 使 `"e"^k = a//b`, `a, b` 为正整数.
	利用引理的函数 `f`, 作
	<span class="formula">
		`F(x) = sum_(i=0)^(2n) (-k)^(2n-i) f^((i))(x)`
		`= sum_(i=0)^oo (-k)^(2n-i) f^((i))(x)`.
	</span>
	求导,
	<span class="formula">
		`F'(x) = sum_(i=0)^oo (-k)^(2n-i) f^((i+1))(x)`
		`= -k sum_(i=1)^oo (-k)^(2n-i) f^((i))(x)`
		`= -k F(x) + k^(2n+1) f(x)`.
	</span>
	从而
	<span class="formula">
		`"d"/dx ["e"^(k x) F(x)] = "e"^(k x) (k F(x) + F'(x))`
		`= "e"^(k x) k^(2n+1) f(x)`.
	</span>
	两边同乘以 `b`, 在 `[0, 1]` 上积分,
	<span class="formula">
		`I = b int_0^1 "e"^(k x) k^(2n+1) f(x) dx`
		`= b "e"^(k x) F(x) dx|_0^1`
		`= b "e"^k F(1) - b F(0) = a F(1) - b F(0)`.
	</span>
	根据引理的 3, `F(0), F(1)` 都为整数, 所以 `I` 是整数. 但是根据引理的
	2, 又有
	<span class="formula">
		`0 lt I lt b "e"^k k^(2n+1)/(n!) = a k^(2n+1)/(n!)`.
	</span>
	只要取 `n` 充分大, 就可使 `a k^(2n+1)/(n!) lt 1`,
	从而 `0 lt I lt 1`, 不可能是整数, 矛盾.
</p>

<p class="corollary">
	`AA q in QQ\\{0}`, `"e"^q` 是无理数.
</p>

<p class="proof">
	显然对任意 `k in ZZ^+`, `"e"^-k` 是无理数, 否则 `"e"^k = 1/("e"^-k)`
	是有理数.
	设 `q = a//b`, `a, b` 为非零整数,
	于是 `"e"^a = "e"^(q b) = ("e"^q)^a`.
	若 `"e"^q` 为有理数, 则 `"e"^a` 为有理数, 矛盾.
</p>

<p class="theorem">
	`pi^2` 是无理数; 从而 `pi` 是无理数.
</p>

<p class="proof">
	(Ivan M. Niven)
	假设 `pi^2 = a//b`, `a, b` 是正整数.
	利用引理的函数 `f`, 构造
	<span class="formula">
		`P(x) = b^n sum_(i=0)^n (-1)^i pi^(2n-2i) f^((2i))(x)`
		`= b^n sum_(i=0)^oo (-1)^i pi^(2n-2i) f^((2i))(x)`,
	</span>
	由于 `b pi^2 = a` 是整数, 再由引理的 3, `P(0), P(1)` 是整数. 求二阶导,
	容易验证
	<span class="formula">
		`P''(x) = -pi^2 P(x) + b^n pi^(2n+2) f(x)`.
	</span>
	从而
	<span class="formula">
		`"d"/dx[P'(x) sin pi x - pi P(x) cos pi x]`
		`= P''(x) sin pi x + pi^2 P(x) sin pi x`
		`= b^n pi^(2n+2) f(x) sin pi x`.
	</span>
	于是, 一方面
	<span class="formula">
		`I = 1/pi int_0^1 b^n pi^(2n+2) sin pi x f(x) dx`
		`= 1/pi [P'(x) sin pi x - pi P(x) cos pi x]_0^1`
		`= P(1) + P(0)`,
	</span>
	故 `I` 为整数. 另一方面, 由引理的 2,
	<span class="formula">
		`0 lt I = pi int_0^1 a^n sin pi x f(x) dx`
		`lt pi a^n/(n!)`.
	</span>
	取 `n` 充分大, 使 `pi a^n/(n!) lt 1`, 从而 `0 lt I lt 1` 不是整数,
	矛盾.
</p>

<p class="theorem">
	<a href="https://www.zhihu.com/question/315450309/answer/620576514">原文来自知乎</a>
	设 `a` 是无理数, 则集合 `{n a mod 1 | n in NN}` 在 `[0, 1]` 上稠密.
	其中 `x mod 1 = x - |__ x__|`, 对正数 `x` 来说, 即为 `x` 的小数部分.
</p>

<p class="proof">
	只需证对任意正整数 `m` 和 `x in [0, 1]`, 存在 `n in ZZ`, 使得
	<span class="formula">
		`|n a mod 1 - x| lt 1/m`.
	</span>
	考虑 `m` 个区间
	<span class="formula">
		`[0, 1/m], [1/m, 2/m], cdots, [(m-1)/m, 1]`
	</span>
	和 `m+1` 个数
	<span class="formula">
		`a mod 1, 2a mod 1, cdots, m a mod 1, (m+1) a mod 1`.
	</span>
	这些数是两两不同的, 否则设 `i a mod 1 = j a mod 1`, 则 `i a - j a in
	ZZ`. 从而 `a = (i a - j a)/(i - j)` 是有理数, 矛盾.
	现在由鸽巢原理, 必有两个不同的数 `i a mod 1, j a mod 1` 属于上面 `m`
	个区间中的同一个区间, `i, j in {1, cdots, m+1}`. 不妨设 `i a mod 1 gt
	j a mod 1`, 有
	<span class="formula">
		`(i-j)a mod 1 = i a mod 1 - j a mod 1 le 1/m`.
	</span>
	记 `y = (i-j)a mod 1`,
	由实数的 Archimedes 性质, 存在正整数 `k` 使得 `k y le x lt (k+1)y`,
	于是
	<span class="formula">
		`|k(i-j)a mod 1 - x| = |k y - x| lt y lt 1/m`.
	</span>
</p>

<p class="example">
	数列 `{tan n}` 无界.
</p>

<p class="proof">
	由于 `1/pi` 是无理数知, `{n/pi mod 1 | n in NN}` 在 `[0, 1]` 上稠密.
	从而对任意 `epsi gt 0`, 存在 `n in NN`, 使得
	<span class="formula">
		`|n/pi mod 1 - 1/2| lt epsi`.
	</span>
	同乘 `pi`,
	<span class="formula">
		`|pi(n/pi mod 1) - pi/2| lt pi epsi`.
	</span>
	又
	<span class="formula">
		`pi(n/pi mod 1) = pi(n/pi - |__n/pi__|) = n - pi|__n/pi__|`,
	</span>
	所以
	<span class="formula">
		`|n - pi(|__n/pi__| + 1/2)| lt pi epsi`.
	</span>
	因为 `|__n/pi__| in NN`, 我们实际证明了:
	集合 `NN` 与集合 `T = {pi/2 + k pi | k in ZZ}` 的距离
	<span class="formula">
		`inf{|x-y|: x in NN, y in T} = 0`.
	</span>
	然而对任意 `y in T`, `x to y` 时有 `tan x to oo`. 所以 `tan n` 无界.
</p>

<h2>连分数</h2>

<p class="example">
  <b>将有理数展为有限简单连分数</b>
  辗转相除, 将 `x` 写为 `[x] + {x}`:
  <span class="formula">
    `62/23 = 2 + 16/23`,<br/>
    `23/16 = 1 + 7/16`,<br/>
    `16/7 = 2 + 2/7`,<br/>
    `7/2 = 3 + 1/2`,
  </span>
  此时分母为 1, 终止迭代. 我们得到
  <span class="formula">
    `62/23 = 2 + 1/(1 + 1/(2 + 1/(3 + 1/2)))`
    `:= [2,1,2,3,2]`.
  </span>
</p>

<p class="example">
  <b>将二次无理数展为循环简单连分数</b>
  仍然是辗转相除:
  <span class="formula">
    `(3+√7)/2 = 2 + (√7-1)/2`,<br>
    `2/(√7-1) = (1+√7)/3 = 1 + (√7-2)/3`,<br>
    `3/(√7-2) = 2+√7 = 4 + √7 - 2`,<br>
    `1/(√7-2) = (2+√7)/3 = 1 + (√7-1)/3`,<br>
    `3/(√7-1) = (1+√7)/2 = 1 + (√7-1)/2`,<br>
  </span>
  余数 `(√7-1)/2` 出现重复, 终止迭代. 我们得到
  <span class="formula">
    `(3+√7)/2 = 2 + 1/(1 + 1/(4 + 1/(1 + 1/(1 + cdots))))`
    `:= [2,bar(1,4,1,1)]`.
  </span>
</p>

<p class="example">
  <b>将连分数写为最简分数</b>
  <span class="formula">
    `[3, 1, 1, 1, 1]`
    `= [3, 1, 1, 2]`
    `= [3, 1, 3/2]`
    `= [3, 5/3]`
    `= 18/5`.
  </span>
</p>

<p class="example">
  <b>贵金属数 (Metallic ratio)</b> 定义为二次方程 `x^2 = n x + 1` 的正根
  <span class="formula">
    `x_n = (n + sqrt(n^2+4))/2`,
  </span>
  `n` 为正整数.  原方程变形为 `x = n + 1/x`, 迭代得到连分数表示:
  <span class="formula">
    `x_n = n + 1/(n+) + 1/(n+) + 1/(n+) cdots`.
  </span>
  黄金数 `x_1 = (1+sqrt 5)/2 = 1.618...`, 白银数 `x_2 = 1 + sqrt 2`,
  青铜数 `x_3 = (3+sqrt(13))/2` 等等.
</p>

<h2>代数数与超越数</h2>

<p class="definition">
	设 `x in CC`, 称 `x` 是一个<b>代数数</b>, 如果 `x`
	是有理数域上某个一元 `n` 次多项式 `f(x)` 的根, `n ge 1`.
	显然有理数是代数数, 称有理数为<b>一次代数数</b>.
	进一步, 如果 `x` 不是任何次数大于等于 `1` 且小于 `n`
	的有理系数的多项式的根, 但它是某个有理系数的 `n` 次多项式的根, 则称
	`x` 是<b>`n` 次代数数</b>.  全体代数数的集合记作 `cc A_QQ`. 称 `x in
	CC` 是<b>超越数</b>, 如果 `x in CC\\cc A_QQ`.
</p>

<p class="remark">
	由于可以将有理系数的 `n` 次多项式的各系数通分,
	所以定义中的有理系数换成整系数也对.
</p>

<p class="theorem">
	全体代数数 `cc A_QQ` 是可数的; 从而由 `CC` 不可数知道, 超越数是存在的,
	而且有不可数多个超越数.
</p>

<p class="proof">
	由于一个 `n` 次多项式至多有 `n` 个不同的根,
	我们只需指出全体整系数多项式的集合 `P` 是可数集.
	以 `P_n` 记全体次数不超过 `n` 的整系数多项式,
	容易用归纳法证明, 对任意非负整数 `n`, `P_n` 是可数的, 于是
		`P = uuu_(n=0)^oo P_n`
	也可数.
</p>

<p class="theorem">
	(Gelfand) 设 `a in cc A_QQ\\{0, 1}`, `b in cc A_QQ\\QQ`, 则 `a^b`
	是超越数.
</p>

<p class="corollary">
	`"e"^pi = ("e"^(pi"i"))^(-"i")` 是超越数.
</p>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
